class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param coins int整型vector
     * @return int整型
     */
    int getCoins(vector<int>& coins) {
        int sz = coins.size();
        if (sz == 1) return coins[0];
        vector<int> copy(1, 1);
        for (auto& e : coins) copy.push_back(e);
        copy.push_back(1);
        coins = copy;
        int len = coins.size();
        vector<vector<int>> dp(len + 1, vector<int>(len + 1, 0));
        for (int i = sz; i >= 1; i--) {
            for (int j = i; j <= sz; j++) {
                for (int k = i; k <= j; k++) {
                    dp[i][j] = max(dp[i][j],
                                   dp[i][k - 1] + dp[k + 1][j] + coins[k] * coins[i - 1] * coins[j + 1]);
                }
            }
        }
        return dp[1][sz];
    }
};